#pragma once
#include <vector>
#include <string>
#include <array>
#include <algorithm>
#include <numeric>

#include <iostream>
#include <iomanip>

using namespace std;

constexpr int table[] = {
    999, 449, 898, 786, 235, 124, 662, 550, 0, 337, 774, 112, 887, 775, 336, 113, 763, 651, 101, 438, 888, 893, 897, 896, 891, 890, 895, 894, 889, 892, 776, 781, 785, 784, 779, 778, 783, 782, 777, 780, 225, 230, 234, 233, 228, 227, 232, 231, 226, 229, 114, 119, 123, 122, 117, 116, 121, 120, 115, 118, 764, 769, 773, 772, 767, 766, 771, 770, 765, 768, 652, 657, 661, 660, 655, 654, 659, 658, 653, 656, 102, 107, 111, 110, 105, 104, 109, 108, 103, 106, 439, 444, 448, 447, 442, 441, 446, 445, 440, 443,
    450, 500, 549, 537, 486, 475, 513, 501, 451, 488, 525, 463, 538, 526, 487, 464, 514, 502, 452, 489, 539, 544, 548, 547, 542, 541, 546, 545, 540, 543, 527, 532, 536, 535, 530, 529, 534, 533, 528, 531, 476, 481, 485, 484, 479, 478, 483, 482, 477, 480, 465, 470, 474, 473, 468, 467, 472, 471, 466, 469, 515, 520, 524, 523, 518, 517, 522, 521, 516, 519, 503, 508, 512, 511, 506, 505, 510, 509, 504, 507, 453, 458, 462, 461, 456, 455, 460, 459, 454, 457, 490, 495, 499, 498, 493, 492, 497, 496, 491, 494,
    899, 949, 998, 986, 935, 924, 962, 950, 900, 937, 974, 912, 987, 975, 936, 913, 963, 951, 901, 938, 988, 993, 997, 996, 991, 990, 995, 994, 989, 992, 976, 981, 985, 984, 979, 978, 983, 982, 977, 980, 925, 930, 934, 933, 928, 927, 932, 931, 926, 929, 914, 919, 923, 922, 917, 916, 921, 920, 915, 918, 964, 969, 973, 972, 967, 966, 971, 970, 965, 968, 952, 957, 961, 960, 955, 954, 959, 958, 953, 956, 902, 907, 911, 910, 905, 904, 909, 908, 903, 906, 939, 944, 948, 947, 942, 941, 946, 945, 940, 943,
    787, 837, 886, 874, 823, 812, 850, 838, 788, 825, 862, 800, 875, 863, 824, 801, 851, 839, 789, 826, 876, 881, 885, 884, 879, 878, 883, 882, 877, 880, 864, 869, 873, 872, 867, 866, 871, 870, 865, 868, 813, 818, 822, 821, 816, 815, 820, 819, 814, 817, 802, 807, 811, 810, 805, 804, 809, 808, 803, 806, 852, 857, 861, 860, 855, 854, 859, 858, 853, 856, 840, 845, 849, 848, 843, 842, 847, 846, 841, 844, 790, 795, 799, 798, 793, 792, 797, 796, 791, 794, 827, 832, 836, 835, 830, 829, 834, 833, 828, 831,
    236, 286, 335, 323, 272, 261, 299, 287, 237, 274, 311, 249, 324, 312, 273, 250, 300, 288, 238, 275, 325, 330, 334, 333, 328, 327, 332, 331, 326, 329, 313, 318, 322, 321, 316, 315, 320, 319, 314, 317, 262, 267, 271, 270, 265, 264, 269, 268, 263, 266, 251, 256, 260, 259, 254, 253, 258, 257, 252, 255, 301, 306, 310, 309, 304, 303, 308, 307, 302, 305, 289, 294, 298, 297, 292, 291, 296, 295, 290, 293, 239, 244, 248, 247, 242, 241, 246, 245, 240, 243, 276, 281, 285, 284, 279, 278, 283, 282, 277, 280,
    125, 175, 224, 212, 161, 150, 188, 176, 126, 163, 200, 138, 213, 201, 162, 139, 189, 177, 127, 164, 214, 219, 223, 222, 217, 216, 221, 220, 215, 218, 202, 207, 211, 210, 205, 204, 209, 208, 203, 206, 151, 156, 160, 159, 154, 153, 158, 157, 152, 155, 140, 145, 149, 148, 143, 142, 147, 146, 141, 144, 190, 195, 199, 198, 193, 192, 197, 196, 191, 194, 178, 183, 187, 186, 181, 180, 185, 184, 179, 182, 128, 133, 137, 136, 131, 130, 135, 134, 129, 132, 165, 170, 174, 173, 168, 167, 172, 171, 166, 169,
    663, 713, 762, 750, 699, 688, 726, 714, 664, 701, 738, 676, 751, 739, 700, 677, 727, 715, 665, 702, 752, 757, 761, 760, 755, 754, 759, 758, 753, 756, 740, 745, 749, 748, 743, 742, 747, 746, 741, 744, 689, 694, 698, 697, 692, 691, 696, 695, 690, 693, 678, 683, 687, 686, 681, 680, 685, 684, 679, 682, 728, 733, 737, 736, 731, 730, 735, 734, 729, 732, 716, 721, 725, 724, 719, 718, 723, 722, 717, 720, 666, 671, 675, 674, 669, 668, 673, 672, 667, 670, 703, 708, 712, 711, 706, 705, 710, 709, 704, 707,
    551, 601, 650, 638, 587, 576, 614, 602, 552, 589, 626, 564, 639, 627, 588, 565, 615, 603, 553, 590, 640, 645, 649, 648, 643, 642, 647, 646, 641, 644, 628, 633, 637, 636, 631, 630, 635, 634, 629, 632, 577, 582, 586, 585, 580, 579, 584, 583, 578, 581, 566, 571, 575, 574, 569, 568, 573, 572, 567, 570, 616, 621, 625, 624, 619, 618, 623, 622, 617, 620, 604, 609, 613, 612, 607, 606, 611, 610, 605, 608, 554, 559, 563, 562, 557, 556, 561, 560, 555, 558, 591, 596, 600, 599, 594, 593, 598, 597, 592, 595,
    1, 51, 100, 88, 37, 26, 64, 52, 2, 39, 76, 14, 89, 77, 38, 15, 65, 53, 3, 40, 90, 95, 99, 98, 93, 92, 97, 96, 91, 94, 78, 83, 87, 86, 81, 80, 85, 84, 79, 82, 27, 32, 36, 35, 30, 29, 34, 33, 28, 31, 16, 21, 25, 24, 19, 18, 23, 22, 17, 20, 66, 71, 75, 74, 69, 68, 73, 72, 67, 70, 54, 59, 63, 62, 57, 56, 61, 60, 55, 58, 4, 9, 13, 12, 7, 6, 11, 10, 5, 8, 41, 46, 50, 49, 44, 43, 48, 47, 42, 45,
    338, 388, 437, 425, 374, 363, 401, 389, 339, 376, 413, 351, 426, 414, 375, 352, 402, 390, 340, 377, 427, 432, 436, 435, 430, 429, 434, 433, 428, 431, 415, 420, 424, 423, 418, 417, 422, 421, 416, 419, 364, 369, 373, 372, 367, 366, 371, 370, 365, 368, 353, 358, 362, 361, 356, 355, 360, 359, 354, 357, 403, 408, 412, 411, 406, 405, 410, 409, 404, 407, 391, 396, 400, 399, 394, 393, 398, 397, 392, 395, 341, 346, 350, 349, 344, 343, 348, 347, 342, 345, 378, 383, 387, 386, 381, 380, 385, 384, 379, 382,
};

class Dinglemouse
{
public:
    static vector<int> sort(const vector<int> &array)
    {
        std::vector<int> sorted(array.size());
        std::partial_sort_copy(array.begin(), array.end(), sorted.begin(), sorted.end(), [](int a, int b){ return table[a] < table[b]; } );
        return sorted;
    }
};

// generate table

const std::string toEng(int n){
    const std::string d0[] = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine" };
    const std::string d1[] = {"ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"};
    const std::string d2[] = {"", "", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"};

    std::string result;
    std::vector<int> dec;

    while( n ){
        dec.push_back( n % 10 );
        n /= 10;
    }

    while( dec.size() < 3 )
        dec.push_back(0);

    switch( dec[2] ){
        case 0: break;
        default: result += d0[dec[2]] + " hundred ";
    }

    switch( dec[1] ){
        case 0:
            switch( dec[0] ) {
                case 0: if( dec[2] == 0 ) result += d0[dec[0]]; break;
                default : result += d0[dec[0]];
            }
            break;
        case 1:
            result += d1[dec[0]];
            break;
        default:
            result += d2[dec[1]] + " ";
            // units
            switch( dec[0] ){
                case 0: break;
                default: result += d0[dec[0]];
            }
    }

    return result;
}

constexpr int LIMIT = 1000;
const std::array<int, LIMIT> convertTable(){

    // fill and sort strings array

    std::array<std::string, LIMIT> stringInt;
    for( int i = 0; i < LIMIT; ++i ){
        stringInt[i] = toEng(i);
    }
    std::sort(stringInt.begin(), stringInt.end(), [](auto a, auto b){ return a.compare(b) < 0; });

    // find and create map

    std::array<int, LIMIT> result;
    std::iota(result.begin(), result.end(), 0);
    std::transform(result.begin(), result.end(), result.begin(), [&stringInt](int a){
        return std::distance(stringInt.begin(), std::find(stringInt.begin(), stringInt.end(), toEng(a)));
    });

    return result;
}
